package leetcode101_xqzhao

// TODO 电话号码的字母组合 【-】 递归+回溯

var phone []string = []string{
	"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz",
}

func letterCombinations(digits string) (ans []string) {
	n := len(digits)
	if n == 0 {
		return
	}

	var phoneDfs func(i int)
	path := make([]byte, n)
	phoneDfs = func(i int) {
		// 回溯结束控制器
		if i == n {
			ans = append(ans, string(path))
			return
		}
		phoneStr := phone[digits[i]-'0']
		for j := 0; j < len(phoneStr); j++ {
			path[i] = byte(phoneStr[j])
			phoneDfs(i + 1)
		}
	}

	phoneDfs(0)
	return
}
